/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.tree
 * author:David
 * Date:2015年6月6日上午11:00:51
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.tree;

/**
 * java实现二叉树(值小于父结点的放左边，大于放右边)
 * @author David since 2015年6月6日 上午11:00:51
 * @version
 * @since JDK 1.6
 */
public class BTree1 {
    private int value;
    private BTree1 left;
    private BTree1 right;

    /**
     * 构造二叉树，放值
     * @param value
     */
    public void store(int value) {
		if (value <= this.value) {
		    if (left == null) {
				left = new BTree1();
				left.value = value;
		    } else {
		    	left.store(value);
		    }
		} else{
		    if (right == null) {
				right = new BTree1();
				right.value = value;
		    } else {
		    	right.store(value);
		    }
		}
    }

    public boolean find(int value) {
		System.out.println("happen" + this.value);
		if (value == this.value) {
		    return true;
		} else if (value > this.value) {
		    if (right == null) {
		    	return false;
		    }
		    return right.find(value);
		} else {
		    if (left == null) {
		    	return false;
		    }
		    return left.find(value);
		}
    }

    /**
     * 先序遍历（访问根结点，先序遍历左子树，先序遍历右子树）
     */
    public void preList() {
		System.out.print(this.value + ",");
		if (left != null) {
		    left.preList();
		}
		if (right != null) {
		    right.preList();
		}
    }

    /**
     * 中序遍历（中序遍历左子树，访问根结点，中序遍历右子树）
     */
    public void middleList() {
		if (left != null) {
		    left.preList();
		}
		System.out.print(this.value + ",");
		if (right != null) {
		    right.preList();
		}
    }
    
    /**
     * 后序遍历（后序遍历左子树，后序遍历右子树，访问根结点）
     */
    public void afterList(){
		if(left!=null){
		    left.preList();
		}
		if(right!=null){
		    right.preList();
		}
		System.out.print(this.value+",");
    }
    
    public static void main(String[] args){
    	System.out.println("=====构建二叉树==========");
		int[] data=new int[]{11,86,9,95,46,87,41,40,48,80,28,55,37,20,97,26,37,50,59,89};
		for(int i=0;i<data.length;i++){
		    System.out.print(data[i]+",");
		}
		BTree1 root=new BTree1();
		root.value=data[0];
		for(int i=1;i<data.length;i++){
		    root.store(data[i]);
		}
		System.out.println("\n=======构建完成==========");
		System.out.println("\n=======先序遍历===========");
		root.preList();
		System.out.println("\n=======中序遍历===========");
		root.middleList();
		System.out.println("\n=======后序遍历===========");
		root.afterList();
		
		System.out.println("\n=======按值查找倒数第二个结点==========");
		root.find(20);
	
    }

}
